package com.Oct_One;

/**
 *980. 不同路径 III
 * 在二维网格 grid 上，有 4 种类型的方格：
 *
 * 1 表示起始方格。且只有一个起始方格。
 * 2 表示结束方格，且只有一个结束方格。
 * 0 表示我们可以走过的空方格。
 * -1 表示我们无法跨越的障碍。
 * 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
 *
 * 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/unique-paths-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/02 16:31
 */

public class Solution980 {

    public int uniquePathsIII(int[][] grid) {
        int step=1;
        int left=0,right=0;
        for (int i=0;i<grid.length;i++)
        {
            for (int j=0;j<grid[0].length;j++)
            {
                if (grid[i][j]==1)
                {
                    left=i;
                    right=j;
                }else if (grid[i][j]==0)
                {
                    step++;
                }
            }
        }
        return backtracking(left,right,step,grid);
    }

    public int backtracking(int i,int j,int step,int[][] grid){
        if (i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==-1) return 0;
        if (grid[i][j]==2) return step==0?1:0;
        grid[i][j]=-1;
        int sum=backtracking(i-1,j,step-1,grid)+backtracking(i+1,j,step-1,grid)+backtracking(i,j-1,step-1,grid)
                +backtracking(i,j+1,step-1,grid);
        grid[i][j]=0;
        System.out.println(sum);
        return sum;
    }

    public static void main(String[] args) {
        Solution980 solution980=new Solution980();
        int[][] grid={
                {1,0,0,0},
                {0,0,0,0},
                {0,0,2,-1}
        };
        System.out.println(solution980.uniquePathsIII(grid));
    }

}
